#include <stdio.h>
#include <string.h>
void getnextarray(char c[],int *next){
    int length=strlen(c);
    next[1]=0;
    int i=1;
    int j=0;
    while(i<length)
    {
        if(j==0||c[i]==c[j]){
            next[++i]=(++j);
        }
        else{
            j=next[j];
        }
    }
    
}
void getnextval(char c[],int *nextval){
    int i=1,j=0;
    nextval[1]=0;
    while(i<strlen(c)){
        if(j==0||c[i]==c[j]){
            ++i;++j;
            if(c[i]!=c[j]){
                nextval[i]=j;
            }
            else{
                nextval[i]=nextval[j];
            }
        }
        else{
            j=nextval[j];
        }
    }
}
void usekmp(char m[],char temp[],int *next){
    int i;i=0;
    int j;j=0;
    while(j<strlen(temp)&&i<strlen(m))
    {
        printf("%d  %d\n",i,j);
        if(m[i]==temp[j]){
            i++;
            j++;
        }
        else if(j>0){
            j=next[j];
        }
        else{
            i++;
        }
    }
    if(j<strlen(temp)){
        printf("主串没有模式串");
    }
    else{
        printf("模式串在主串的第%d开始",i-strlen(temp));
    }
}
void main(){
    char m[]="aabaaacbaabaabaabcababababab";
    char temp[]="abaabcaba";
    int next[100];
    int nextval[100];
    printf("%s\n",m);
    getnextarray(temp,next);
    printf("%d\n",next[1]);
    getnextval(temp,nextval);
    printf("%d\n",nextval[1]);
    usekmp(m,temp,next);
    usekmp(m,temp,nextval);
}